class MinHeap:
    def __init__(self, array=None):
        self.heap = []
        if array is not None:
            self.heap = array
            self._build_heap()
    
    def _build_heap(self):
        """从无序列表构建最小堆"""
        n = len(self.heap)
        # 从最后一个非叶子节点开始向前遍历
        for i in range(n // 2 - 1, -1, -1):
            self._heapify_down(i)
    
    def _heapify_down(self, index):
        """从指定位置向下堆化"""
        n = len(self.heap)
        smallest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        # 找到当前节点、左子节点、右子节点中的最小值
        if left < n and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < n and self.heap[right] < self.heap[smallest]:
            smallest = right
        
        # 如果最小值不是当前节点，则交换并继续向下堆化
        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._heapify_down(smallest)
    
    def _heapify_up(self, index):
        """从指定位置向上堆化"""
        parent = (index - 1) // 2
        if parent >= 0 and self.heap[index] < self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            self._heapify_up(parent)
    
    def insert(self, value):
        """插入新元素并维护堆结构"""
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)
    
    def extract_min(self):
        """移除并返回堆顶最小值"""
        if not self.heap:
            return None
        
        min_val = self.heap[0]
        last = self.heap.pop()
        
        if self.heap:
            self.heap[0] = last
            self._heapify_down(0)
        
        return min_val
    
    def peek(self):
        """查看堆顶最小值（不删除）"""
        return self.heap[0] if self.heap else None
    
    def size(self):
        """返回堆中元素数量"""
        return len(self.heap)
    
    def is_empty(self):
        """检查堆是否为空"""
        return len(self.heap) == 0
    

if __name__ == "__main__":
    # 创建空堆并插入元素
    heap = MinHeap()
    heap.insert(5)
    heap.insert(2)
    heap.insert(8)
    heap.insert(1)
    heap.insert(3)

    print(heap.extract_min())  # 输出: 1
    print(heap.extract_min())  # 输出: 2
    print(heap.peek())         # 输出: 3

    # 从现有列表构建堆
    arr = [9, 4, 6, 2, 7]
    heap2 = MinHeap(arr)
    print(heap2.extract_min())  # 输出: 2
    print(heap2.extract_min())  # 输出: 4    


"""
void shift_up(int * arr, int n){
    while (n > 1 && arr[n / 2] < arr[n]) {
        swap(arr, n/2, n);
        n /= 2;
    }
}

父节点位置：parent(i) = (i-1)//2

左子节点：left(i) = 2*i + 1

右子节点：right(i) = 2*i + 2


def _heapify_up(self, index):
    # 递归实现向上调整
    if index == 0:  # 基准情况：到达根节点
        return
    
    parent = (index - 1) // 2
    # 如果当前节点值小于父节点值
    if self.heap[index] < self.heap[parent]:
        # 交换父子节点
        self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
        # 递归向上调整
        self._heapify_up(parent)


"""    